package com.zsj.graph;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * @author zsj
 * @version 1.0
 * @date 2024/6/2 16:58
 * @description Dijkstra算法
 * 这是一个有向图的最短路径算法
 */
public class Dijkstra {

    /**
     * dijkstra 算法
     *
     * @param head 出发节点
     * @description 注意此算法要求边的权值不能有负数
     */
    public static HashMap<Node, Integer> dijkstra(Node head) {
        //从这个head到其它节点最小的距离
        //key:  head出发到达的key
        //value:head出发到达key的最短距离
        //如果在表中 没有T的记录 韩式是从head出发到这个T点的距离是正无穷大
        HashMap<Node, Integer> distanceMap = new HashMap<>();
        //初始化 除了节点自己 其它的到达距离都是正无穷大
        distanceMap.put(head, 0);
        //已经求过距离的点 存在selectedNodes中 以后再也不碰
        HashSet<Node> selectedNodes = new HashSet<>();
        //找到最小的节点且没有被选中过的
        Node minNode = getMinAndUnselectedNode(distanceMap, selectedNodes);

        while (minNode != null) {
            //得到这个最短路径的节点的边的权值
            Integer distance = distanceMap.get(minNode);
            for (Edge edge : minNode.edges) {
                //对这个最小节点的边进行遍历 每次都得到它的to方向
                Node toNode = edge.to;
                //如果这个点在distanceMap中没有出现过 说明这个距离之前是正无穷
                //我们总是可以更新
                if (!distanceMap.containsKey(toNode)) {
                    //记录
                    distanceMap.put(toNode, distance + edge.weight);
                } else {
                    //我们选择那个较小的值
                    distanceMap.put(edge.to,
                            Math.min(distanceMap.get(toNode),
                                    distance + edge.weight));
                }
            }
            //将这个值进行标记 不再使用
            selectedNodes.add(minNode);
            //继续选择
            minNode = getMinAndUnselectedNode(distanceMap, selectedNodes);
        }
        return distanceMap;
    }

    private static Node getMinAndUnselectedNode(HashMap<Node, Integer> distanceMap,
                                                HashSet<Node> selectedNodes) {
        Node result = null;
        Integer minDistance = Integer.MAX_VALUE;//默认权值为正无穷大 如果取值范围比这个大 那你就修改为long类型
        for (Map.Entry<Node, Integer> entry : distanceMap.entrySet()) {
            Node key = entry.getKey();//获取到这个里面的节点
            Integer value = entry.getValue();//获取到它的权值
            if (!selectedNodes.contains(key) &&
                    //如果被选择的集合中不包含 并且这个权值是更小的值时重新指定
                    value < minDistance) {
                result = key;
                minDistance = value;
            }
        }
        return result;
    }


}
